#include <iostream>
using namespace std;

void print_array(int a[],int n){
	for(int i = 0;i < n;i++){
		cout << a[i] << " ";
	}
	cout <<endl;
}
void merge(int arr[],int tempArr[],int left,int mid,int right){
	int l_pos = left;
	int r_pos = mid+1;
	int pos = left;
	
	while(l_pos <= mid && r_pos <= right){
		if(arr[l_pos] < arr[r_pos]){
			tempArr[pos++] = arr[l_pos++]; 
		}else{
			tempArr[pos++] = arr[r_pos++];
		}
	}
	while(l_pos <= mid){
		tempArr[pos++] = arr[l_pos++];
	}
	while(r_pos <= right){
		tempArr[pos++] = arr[r_pos++];
	}
	while(left <= right){
		arr[left] = tempArr[left];
		left++;
	}
}


void msort(int arr[],int tempArr[],int left,int right){
	if(left <right){
		int mid = (left+right)/2;
		msort(arr,tempArr,left,mid);
		msort(arr,tempArr,mid+1,right);
		merge(arr,tempArr,left,mid,right);
	}
	
}

void merge_sort(int arr[],int n){
	int* tempArr = new int[n];
	msort(arr,tempArr,0,n-1);
	delete tempArr;
}

int main(){
	
	int arr[] = {9,5,2,7,12,4,3,1,11};
	int n = 9;
	print_array(arr,n);
	merge_sort(arr,n);
	print_array(arr,n);
	
	
	return 0;
}

